package com.cll.learn.stage10.dp;

import java.util.*;

/**
 * 描述信息:
 *
 * @author CLL
 * @version 1.0
 * @date 2021/5/14 8:02
 */
public class Demo01 {

    /**
     * 计算0-1背包问题
     * @param max   背包的最大承重
     * @param weight    商品的重量数组
     * @param value 商品的价值数组
     * @return  背包能够容纳的最大价值
     */
    private static int maxPackage(int max, int[] weight, int[] value){
        if (max <= 0) {
            return 0;
        }
        if (null == value || 0 == value.length) {
            return 0;
        }
        if (null == weight || 0 == weight.length) {
            return 0;
        }
        if (weight.length != value.length) {
            return 0;
        }
        /*
        构造db二维数组,给dp二维数组赋值完成，结果就出来了
        行：容纳物品数量
        列：背包的承重
         */
        int[][] dp = new int[value.length + 1][max + 1];
        for (int i = 1; i <= value.length; i++) {
            Set<Integer> result = new HashSet<>();
            for (int j = 1; j <=  max; j++) {
                // 当前物品大于当前背包的最大承重
                if (weight[i-1] > j) {
                    dp[i][j] = dp[i-1][j];
                } else {
                    // 可以选择物品
                    int notSelect = dp[i-1][j];
                    int select = value[i-1] + dp[i-1][j-weight[i-1]];
                    int currentMax = Math.max(notSelect, select);
                    if (currentMax == select) {
                        result.add(i-1);
                    }
                    dp[i][j] = currentMax;
                }
            }
            System.out.println("本轮选中物品信息如下");
            for (int k : result) {
                System.out.println("weight = " + weight[k] + "<==> value = " + value[k]);
            }
        }

        return dp[value.length][max];
    }

    public static void main(String[] args) {
        int max = 10;
        int[] weight = new int[]{2,2,6,5,4};
        int[] value = new int[]{6,3,5,4,6};

        int maxPackage = maxPackage(max, weight, value);
        System.out.println("result = " + maxPackage);
    }
}
